package cn.edu.buaa.sei.jdat.search.trie;

import java.util.ArrayList;
import java.util.List;

public class DomainTree<T> {
	private DomainNode<T> root;
	
	public DomainTree() {
		root = new DomainNode<T>(null);
	}
	
	/**
	 * Split name-space by dots. For example, a name-space "com.a.b", the return should be
	 * [com, a, b]. The empty string wouldn't be overlooked.
	 * @param namespace
	 * @return
	 */
	public static String[] splitNamespace(String namespace) {
		ArrayList<String> tokens = new ArrayList<String>();
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < namespace.length(); i++) {
			char ch = namespace.charAt(i);
			if (ch == '.') {
				tokens.add(sb.toString());
				sb.setLength(0);
			}
			else
				sb.append(ch);
		}
		tokens.add(sb.toString());
		return tokens.toArray(new String[0]);
	}
	
	/**
	 * Concatenate two tokens into one name-space with a dot between them.
	 * @param pred
	 * @param succ
	 * @return
	 */
	private static String concatName(String pred, String succ) {
		StringBuffer sb = new StringBuffer();
		if (pred == null)
			return succ;
		if (succ == null)
			return pred;
		sb.append(pred).append('.').append(succ);
		return sb.toString();
	}
	
	/**
	 * Get all name-spaces in this tree.
	 * @return
	 */
	public List<ItemData<T>> getAllDomains() {
		List<ItemData<T>> list = new ArrayList<ItemData<T>>();
		getDomains(root, list, null);
		return list;
	}
	
	/**
	 * Get all name-spaces that have the specific prefix.
	 * @param prefix
	 * @return
	 */
	public List<ItemData<T>> getDomains(String prefix) {
		List<ItemData<T>> list = new ArrayList<ItemData<T>>();
		List<DomainNode<T>> nodes = getMatchedNodes(prefix);
		String word = prefix.substring(0, prefix.lastIndexOf('.'));
		for (DomainNode<T> node : nodes) {
			getDomains(node, list, word);
		}
		return list;
	}
	
	/**
	 * Get name-spaces that must have an accurate prefix. For example, if there are
	 * "com.aa.bbb" and "com.ab.ccc" in this tree, if the prefix is "com.a", this method
	 * return none, while the prefix is "com.aa" this method return "com.aa.bbb".
	 * @param prefix
	 * @return
	 */
	public List<ItemData<T>> getDomainsStrictly(String prefix) {
		List<ItemData<T>> list = new ArrayList<ItemData<T>>();
		DomainNode<T> node = getNode(prefix);
		getDomains(node, list, prefix);
		return list;
	}
	
	/**
	 * Get name-spaces that below (belong to) the given node's name-space. The prefix
	 * is just used to return the complete and correct data.
	 * @param node
	 * @param prefix
	 * @return
	 */
	public List<ItemData<T>> getDomainsStrictly(DomainNode<T> node, String prefix) {
		List<ItemData<T>> list = new ArrayList<ItemData<T>>();
		getDomains(node, list, prefix);
		return list;
	}

	private void getDomains(DomainNode<T> node, List<ItemData<T>> list, String prefix) {
		if (node == null)
			return;
		String head = concatName(prefix, node.name);
		if (node.data != null)
			list.add(new ItemData<T>(head, node.data));
		if (node.children != null) {
			for (DomainNode<T> n : node.children) {
				getDomains(n, list, head);
			}
		}
	}
	
	/**
	 * An advanced method for search optimization. Get node with correct name-space.
	 * @param namespace
	 * @return
	 */
	public DomainNode<T> getNode(String namespace) {
		return getNode(root, namespace);
	}
	
	/**
	 * An advanced method for search optimization. Get node with correct name-space suffix.
	 * @param namespace
	 * @return
	 */
	public DomainNode<T> getNode(DomainNode<T> start, String suffix) {
		if (start == null)
			return null;
		DomainNode<T> node = start;
		boolean flag = false;
		String[] tokens = splitNamespace(suffix);
		for (int i = 0; i < tokens.length; i++) {
			if (node.children == null)
				return null;
			for (DomainNode<T> n : node.children) {
				if (tokens[i].equals(n.name)) {
					node = n;
					flag = true;
					break;
				}
			}
			if (flag == false)
				return null;
			flag = false;
		}
		return node;
	}
	
	public DomainNode<T> getChild(DomainNode<T> parent, String token) {
		if (parent == null)
			parent = root;
		if (parent.children == null)
			return null;
		for (DomainNode<T> n : parent.children) {
			if (token.equals(n.name))
				return n;
		}
		return null;
	}
	
	/**
	 * Get matched nodes with name-space, start from specific node.
	 * @param suffix
	 * @param start
	 * @return
	 */
	public List<DomainNode<T>> getMatchedNodes(DomainNode<T> start, String suffix) {
		if (start == null)
			return null;
		ArrayList<DomainNode<T>> list = new ArrayList<DomainNode<T>>();
		if (start.children == null)
			return null;
		for (DomainNode<T> n : start.children) {
			if (n.name.contains(suffix))
				list.add(n);
		}
		return list;
	}
	
	/**
	 * Get matched nodes with name-space.
	 * @param prefix
	 * @return
	 */
	public List<DomainNode<T>> getMatchedNodes(String prefix) {
		ArrayList<DomainNode<T>> list = new ArrayList<DomainNode<T>>();
		DomainNode<T> node = root;
		boolean flag = false;
		String[] tokens = splitNamespace(prefix);
		for (int i = 0; i < tokens.length - 1; i++) {
			if (node.children == null)
				return null;
			for (DomainNode<T> n : node.children) {
				if (tokens[i].equals(n.name)) {
					node = n;
					flag = true;
					break;
				}
			}
			if (flag == false)
				return null;
			flag = false;
		}
		if (node.children == null)
			return null;
		for (DomainNode<T> n : node.children) {
			if (n.name.contains(tokens[tokens.length - 1]))
				list.add(n);
		}
		return list;
	}
	
	public T get(String namespace) {
		DomainNode<T> node = getNode(namespace);
		return node == null ? null : node.data;
	}
	
	public boolean contains(String namespace) {
		return getNode(namespace) == null;
	}
	
	public void add(String word, T data) {
		DomainNode<T> node = root;
		boolean flag = false;
		String[] tokens = splitNamespace(word);
		for (int i = 0; i < tokens.length; i++) {
			if (node.children == null) {
				node.add(new DomainNode<T>(tokens[i]));
				node = node.children.get(0);
				continue;
			}
			// search next token
			for (DomainNode<T> n : node.children) {
				if (tokens[i].equals(n.name)) {
					node = n;
					flag = true;
					break;
				}
			}
			if (flag == false) {
				DomainNode<T> n = new DomainNode<T>(tokens[i]);
				node.add(n);
				node = n;
			}
			flag = false;
		}
		node.data = data;
	}
	
	public void remove(String word) {
		ArrayList<DomainNode<T>> path = new ArrayList<DomainNode<T>>();
		DomainNode<T> node = root;
		boolean flag = false;
		String[] tokens = splitNamespace(word);
		for (int i = 0; i < tokens.length; i++) {
			path.add(node);
			if (node.children == null )
				return;
			// search next token
			for (DomainNode<T> n : node.children) {
				if (tokens[i].equals(n.name)) {
					node = n;
					flag = true;
					break;
				}
			}
			if (flag == false)
				return;
			flag = false;
		}
		if (node.children != null && node.children.size() != 0) {
			node.data = null;
			return;
		}
		for (int i = path.size() - 1; i >= 0; i--) {
			DomainNode<T> n = path.get(i);
			n.children.remove(node);
			if (n.children.size() != 0 || n.data != null)
				return;
		}
	}
}
